package com.practice.tree;

import java.util.ArrayList;

import com.practice.util.BinaryTreeNode;
import com.practice.util.BinaryTree;

/**
 * Given preorder and inorder traversal of a tree, construct the binary tree. (G)
 * Assumption: no duplicate value in tree.
 * 
 */
public class BuildBST {
	public BinaryTree construct(int[] preorder, int[] inorder) {
		BinaryTreeNode root = buildTree(preorder, 0, preorder.length, 
				inorder, 0, inorder.length);
		return new BinaryTree(root);
	}
	
	private BinaryTreeNode buildTree(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
		if (s1 == e1) return null;
		
		int root = preorder[s1];
		BinaryTreeNode parent = new BinaryTreeNode(null, root);
		
		int offset = offset(inorder, s2, e2, root);
		parent.addLeft(buildTree(preorder, s1+1, s1+1+offset, 
				inorder, s2, s2+offset));
		parent.addRight(buildTree(preorder, s1+1+offset, e1, 
				inorder, s2+1+offset, e2));
		
		return parent;
	}
	
	private int offset(int[] a, int start, int end, int value) {
		for (int i=start; i<end; i++) {
			if (a[i] == value) return i-start;
		}
		return -1;
	}
	
	public int[] preorder(BinaryTree tree) {
		return new Traverse() {
			public void traverse(ArrayList<Integer> t, BinaryTreeNode node) {
				if (node == null) return;
				t.add(node.value());
				traverse(t, node.left());
				traverse(t, node.right());
			}
		}.traverse(tree);
	}
	
	public int[] inorder(BinaryTree tree) {
		return new Traverse() {
			public void traverse(ArrayList<Integer> t, BinaryTreeNode node) {
				if (node == null) return;
				traverse(t, node.left());
				t.add(node.value());
				traverse(t, node.right());
			}
		}.traverse(tree);
	}
	
	public int[] postorder(BinaryTree tree) {
		return new Traverse() {
			public void traverse(ArrayList<Integer> t, BinaryTreeNode node) {
				if (node == null) return;
				traverse(t, node.left());
				traverse(t, node.right());
				t.add(node.value());
			}
		}.traverse(tree);
	}
	
	private abstract class Traverse {
		public abstract void traverse(ArrayList<Integer> t, BinaryTreeNode node);
		
		public int[] traverse(BinaryTree tree) {
			ArrayList<Integer> t = new ArrayList<Integer>();
			
			traverse(t, tree.getRoot());
			
			int[] a = new int[t.size()];
			for (int i=0; i<t.size(); i++) {
				a[i] = t.get(i);
			}
			
			return a;
		}
	}
}
